package 算法思维系列;

import java.util.LinkedList;
import java.util.List;

public class 煎饼排序_969 {

    List<Integer> res = new LinkedList<>();

    public List<Integer> pancakeSort(int[] arr) {
        sort(arr, arr.length);
        return res;
    }

    // 将前n块烧饼排序
    public void sort(int[] arr, int n) {
        if (n == 1) {
            return;
        }

        //寻找最大烧饼的索引
        int maxCake = 0;
        int maxCakeIndex = 0;

        for (int i = 0; i < n; i++) {
            if (arr[i] > maxCake) {
                maxCake = arr[i];
                maxCakeIndex = i;
            }
        }
        //把最大的烧饼反转到顶部
        reverse(arr, 0, maxCakeIndex);
        //记录下标。注意要比正常下标多1
        res.add(maxCakeIndex + 1);
        //再把最大烧饼反转到底部
        reverse(arr, 0, n - 1);
        res.add(n);

        //递归调用，翻转剩下的烧饼
        sort(arr, n - 1);


    }

    public void reverse(int[] arr, int i, int j) {
        while (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
}
